package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 二叉树中和为某一值的路径
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * 叶子节点 是指没有子节点的节点。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9834.%20%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%92%8C%E4%B8%BA%E6%9F%90%E4%B8%80%E5%80%BC%E7%9A%84%E8%B7%AF%E5%BE%84/README
 */
public class P34 {

    class Solution {

        private List<List<Integer>> res;
        private List<Integer> path;

        public List<List<Integer>> pathSum(TreeNode root, int sum) {
            if (root == null) {
                return Collections.emptyList();
            }
            res = new ArrayList<>();
            path = new ArrayList<>();
            dfs(root, sum);
            return res;
        }

        private void dfs(TreeNode root, int target) {
            if (root == null) {
                return;
            }
            path.add(root.value);
            target = target - root.value;
            if (target == 0 && root.left == null && root.right == null) {
                res.add(new ArrayList<>(path));
            }
            dfs(root.left, target);
            dfs(root.right, target);
            path.remove(path.size() -1);
        }

    }
}
